// Tags: String, Math, Factor
#include <cstdio>

typedef unsigned long long ull;
const int N = 5e5 + 5, base = 29;
int pri[N], fac[N], stk[N], top, cnt, q, n;
char str[N];
bool vis[N];
ull hash[N], qpow[N] = {1};

inline ull gethash(int x, int len) {
  return hash[x + len - 1] - hash[x - 1] * qpow[len];
}

inline bool check(int x1, int x2, int len) {
  return gethash(x1, len) == gethash(x2, len);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("P3538 [POI2012]OKR-A Horrible Poem.in", "r", stdin);
  freopen("P3538 [POI2012]OKR-A Horrible Poem.out", "w", stdout);
#endif
#endif

  scanf("%d%s%d", &n, str, &q);
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      pri[++cnt] = i;
      fac[i] = i;
    }
    for (int j = 1; j <= cnt && pri[j] * i <= n; ++j) {
      vis[i * pri[j]] = true;
      fac[i * pri[j]] = pri[j];
      if (i % pri[j] == 0) break;
    }
  }
  for (int i = 0; i < n; ++i) {
    hash[i] = hash[i - 1] * base + str[i] - 'a' + 1;
  }
  for (int i = 1; i <= n; ++i) { qpow[i] = qpow[i - 1] * base; }
  for (int i = 1, a, b, len; i <= q; ++i) {
    scanf("%d%d", &a, &b);
    a--, b--;
    len = b - a + 1, top = 0;
    while (len != 1) {
      stk[++top] = fac[len];
      len /= fac[len];
    }
    len = b - a + 1;
    for (int j = 1, tmp; j <= top; ++j) {
      tmp = len / stk[j];
      if (check(a, a + tmp, b - a + 1 - tmp)) len /= stk[j];
    }
    printf("%d\n", len);
  }
  return 0;
}